#include <cstdio>
#include <algorithm>
using namespace std;
/*
 * 对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目 φ(1)=1
 */
//直接求解
//将n分解为多个素因子的若干次幂之和，即n=(p1^ai)...(pk^ak)
//欧拉函数phi(n)=n(1-1/p1)...(1-1/pk)
int Euler(int n){
	int res=n;
	int a=n;
	for(int i=2;i*i<=a;i++){
		if(a%i==0){
			//先除再乘防止溢出
			res=res/i*(i-1);
			//除掉这个质因子的多次幂，类似于素数筛，比如i=2 除掉幂之后，后面i=4就跳过了
			while(a%i==0){
				a/=i;
			}
		}
	}
	//处理剩下的因数
	if(a>1){
		res=res/a*(a-1);
	}
	return res;
}
//筛法
const int MAXN=10050;
int euler[MAXN];
void Init(){
	for(int i=1;i<MAXN;i++){
		euler[i]=i;
	}
	for(int i=2;i<MAXN;i++){
		if(euler[i]==i){
			for(int j=i;j<MAXN;j+=i){
				euler[j]=euler[j]/i*(i-1);
			}
		}
	}
}
int main(void){
	Init();
	for(int i=1;i<=15;i++){
		printf("%d %d\n",Euler(i),euler[i]);
	}
	return 0;
}
